package com.demo.datastructure.skipList;

import java.util.Arrays;

/**
 * @description: 跳表的java实现
 * @author: ljr
 * @time: 2021/5/15 13:22
 */
public class SkipListDemo {

    private static final float SKIPLIST_P = 0.5f;

    private static final  int MAX_LEVEL = 16;

    private int levelCount = 1;

    private final Node head = new Node();

    public Node find(int value){
        Node p = head;
        for(int i = levelCount-1; i > 0; --i){
            while (p.frowards[i] != null && p.frowards[i].data < value){
                p = p.frowards[i];
            }
        }

        if(p.frowards[0] != null && p.frowards[0].data == value){
            return p.frowards[0];
        }else{
            return null;
        }
    }

    public void insert(int value){
        int level = randomLevel();
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;
        Node[] update = new Node[level];
        for(int i = 0; i < level; ++i){
            update[i] = head;
        }

        Node p = head;
        for(int i = level-1; i >=0; --i){
            while (p.frowards[i] != null && p.frowards[i].data < value){
                p = p.frowards[i];
            }
            update[i] = p;
        }

        for(int i = 0; i < level; ++i){
            newNode.frowards[i] = update[i].frowards[i];
            update[i].frowards[i] = newNode;
        }

        if(levelCount < level) levelCount = level;

    }


    // 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
    // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
    // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
    //        50%的概率返回 1
    //        25%的概率返回 2
    //      12.5%的概率返回 3 ...
    private int randomLevel(){
        int level = 1;
        while (Math.random() <SKIPLIST_P && level < MAX_LEVEL)
            level+=1;

        return level;
    }


    public class Node{
        private int data = -1;
        private final Node[] frowards = new Node[MAX_LEVEL];
        private int maxLevel = 0;

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("{ data:");
            sb.append(data);
            sb.append("; levels: ");
            sb.append(maxLevel);
            sb.append(" }");
            return sb.toString();
        }
    }


    public static void main(String[] args) {
        SkipListDemo listDemo = new SkipListDemo();
        listDemo.insert(5);

    }
}
